package com.sheng.leetcode.year2022.month06.day02;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/06/02
 *
 * 450. 删除二叉搜索树中的节点
 *
 * 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，
 * 并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
 * 一般来说，删除节点可分为两个步骤：
 * 首先找到需要删除的节点；
 * 如果找到了，删除它。
 *
 * 示例 1:
 *
 * 输入：root = [5,3,6,2,4,null,7], key = 3
 * 输出：[5,4,6,2,null,null,7]
 * 解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
 * 一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
 * 另一个正确答案是 [5,2,6,null,4,null,7]。
 *
 * 示例 2:
 *
 * 输入: root = [5,3,6,2,4,null,7], key = 0
 * 输出: [5,3,6,2,4,null,7]
 * 解释: 二叉树不包含值为 0 的节点
 * 示例 3:
 *
 * 输入: root = [], key = 0
 * 输出: []
 *
 * 提示:
 *
 * 节点数的范围 [0, 104].
 * -105 <= Node.val <= 105
 * 节点值唯一
 * root 是合法的二叉搜索树
 * -105 <= key <= 105
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/delete-node-in-a-bst
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0450 {

    @Test
    public void test01(){
        TreeNode root = new TreeNode(5);
        TreeNode left = new TreeNode(3);
        left.left = new TreeNode(2);
        left.right = new TreeNode(4);
        TreeNode right = new TreeNode(6);
        right.right = new TreeNode(7);
        root.left = left;
        root.right = right;
        int key = 3;
        TreeNode treeNode = new Solution().deleteNode(root, key);
        System.out.println(treeNode);
    }

}

//Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return root;
        }
        //遍历，找到val值和key相等的结点的位置
        TreeNode ergodic = ergodic(root, key);
        return ergodic;
    }

    public TreeNode ergodic(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        //判断val值是否等于key，相等则代表找到了对应结点
        if (root.val == key) {
            //如果该结点左右结点都为空，则直接返回空
            if (root.left == null && root.right == null) {
                return null;
            //如果左结点不为空，右结点为空，则返回左结点替换原结点的位置
            } else if (root.left != null && root.right == null) {
                return root.left;
            //如果右结点不为空，左结点为空，则返回右结点替换原结点的位置
            } else if (root.left == null && root.right != null) {
                return root.right;
            } else {
                //左右子结点都不为空，则将左结点移动到右结点的最左子节点，然后返回右结点，或者将右结点移动到左结点的最右子节点，然后返回
                TreeNode treeNode = root.left;
                TreeNode min = min(root.right);
                min.left = treeNode;
                return root.right;
            }
        } else {
            //根据二叉搜索树的规律进行查找
            if (root.val < key) {
                TreeNode ergodic = ergodic(root.right, key);
                root.right = ergodic;
                return root;
            } else {
                TreeNode ergodic = ergodic(root.left, key);
                root.left = ergodic;
                return root;
            }
        }
    }

    //或者二叉树的最左子结点，然后返回
    public TreeNode min(TreeNode root) {
        if (root.left == null) {
            return root;
        }
        return min(root.left);
    }
}
